public class Trie {
	
	TrieNode root;
	
	public Trie() {
		this.root = new TrieNode();
	}
	
	public void insert(String word) {
		if(word==null) {
			return;
		}
		TrieNode cur = root;
		char[] words = word.toCharArray();
		for(char c : words) {
			int index = c-'a';
			if(cur.nexts[index]==null) {
				cur.nexts[index] = new TrieNode();
			} 
			cur.pass++;
			cur = cur.nexts[c-'a'];
		}
		cur.end++;
	}
	
	public int search(String word) {
		if(word==null) {
			return 0;
		}
		TrieNode cur = root;
		char[] words = word.toCharArray();
		for(char c : words) {
			int index = c-'a';
			if(cur.nexts[index]==null) {
				return 0;
			}
			cur = cur.nexts[index];
		}
		return cur.end;
	}
	
	public void delete(String word) {
		if(search(word)<=0) {
			return;
		}
		TrieNode cur = root;
		char[] words = word.toCharArray();
		cur.pass--;
		for(char c : words) {
			int index = c - 'a';
			if(--cur.nexts[index].pass==0) {
				cur.nexts[index]=null;
				return;
			}
			cur = cur.nexts[index];
		}
		cur.end--;
	}
	
	public int prefixNumber(String pre) {
		if(pre==null) {
			return 0;
		}
		TrieNode cur = root;
		char[] pres = pre.toCharArray();
		for(char c : pres) {
			int index = c-'a';
			if(cur.nexts[index]==null) {
				return 0;
			}
			cur = cur.nexts[index];
		}
		return cur.pass;
	}
	
}
